Appendix F — Assignment F (R: Lists and Recursion)

R: Lists and recursion

Instructions

You may talk to a friend, discuss the questions and potential directions for solving them. However, you need to write your own solutions and code separately, and not as a group activity.
Do not write your name on the assignment.
Make R code chunks to insert code and type your answer outside the code chunks. Ensure that the solution is written neatly enough to understand and grade.
Render the file as HTML to submit.
There are 5 points for clealiness and organization. The code should be commented and clearly written with intuitive variable names. For example, use variable names such as number_input, factor, hours, instead of a,b,xyz, etc.
The assignment is worth 100 points, and is due on 30th May 2023 at 11:59 pm.
You are not allowed to use a for loop in this assignment, except in the last question on Sudoku.

F.1 TED Talks

Execute the following code to get the object ted_talks, which contains information about TED talks.

Note that you are not allowed to use a for loop or any other kind of loop in all the questions below.

library(rjson)
ted_talks<-fromJSON(file='TED_Talks.json')

F.1.1 Number of talks

How many TED talks are there in the data?

(2 points)

F.1.2 Average number of views

What is the mean number of views of the TED talks?

Reminder: Do not use a for loop or any other kind of loop.

(4 points)

F.1.3 Highest number of views

Find the headline, year_filmed, and number of views of the top five talks with the highest number of views.

Reminder: Do not use a for loop or any other kind of loop.

(6 points)

F.1.4 Most fascinating votss

Find the headline, year_filmed and count of Funny votes of the top five talks with the highest number of Funny votes

Reminder: Do not use a for loop or any other kind of loop.

(8 points)

F.1.5 Highest proportion of Inspiring votes

Find the headline, year_filmed, and proportion of Inspiring votes from among all the votes for the talk, of the top five talks with the highest proportion of Inspiring votes.

Reminder: Do not use a for loop or any other kind of loop.

(10 points)

F.1.6 Most popular voting category

Add the votes of all TED talks for each category. Which category has received the most votes? What is the proportion of total votes for this category?

Reminder: Do not use a for loop or any other kind of loop.

(10 points)

F.2 Recursive binary search

Execute the code below to get the object wordlist_global, which contains a vector of words. Write a recursive function that accepts a word, say word_to_search and a vector of words, say wordlist as arguments, and finds if the word_to_search occurs in wordlist_global or not. This is very simple to do with the code word_to_search %in% tuple_of_words. However, this code is unfortunately very slow.

As the words in the wordlist_global are already sorted in alphabetical order, we can search using a faster way, called binary search. To implement binary search in a function, start by comparing word_to_search with the middle entry in the wordlist_global. If they are equal, then you are done and the function should return True. On the other hand, if the word_to_search comes before the middle entry, then the function must call itself to search the first half of wordlist_global. If it comes after the middle entry, then the function must call itself to search the second half of wordlist_global. In every recursive call, the function must repeat the process on the appropriate half of the wordlist and continue until the word is found or there is nothing left to search, in which case the function short return False. The < and > operators can be used to alphabetically compare two character objects.

Note that your function must use recursion.

F.2.1 Word search

Check your function if the word_to_search is:

'agreement'
'qualifier'
'agree'

wordlist_global<-unlist(read.table('wordlist.txt', header = FALSE, sep = "", dec = "."))

(6 points)

F.2.2 Number of iterations

Update the function to also print the number of iterations it took to find the word_to_search or fail in finding the word_to_search.

Check your function if the word_to_search is:

'agreement'
'tiring'

(8 points)

F.2.3 Index of `word_to_search`

Update the function in the previous question to also print the index of word_to_search in wordlist_global if the word is found. For example, the index of ‘abacus’ is 1, the index of ‘abdomen’ is 2, and so on.

Check your function if the word_to_search is:

'agreement'
'skirmish'

(10 points)

F.3 Sudoku

This question is about solving the Sudoku puzzle with recursion. Read about the Sudoku rules here. Think about how to solve the Sudoku puzzle with recursion.

This blog provides a recursive function solve_sudoku to solve the Sudoku puzzle. Read the blog and understand how the function is implemented. You will need to add some lines in the code to answer some of the questions below.

F.3.1 Base case & recursive case

What are the base and recursive cases of the function? Cite the relevant lines of code, and explain.

(4 points)

F.3.2 Solving Sudoku

Use the function to solve the following Sudoku puzzle. Execute the following lines of code to see the puzzle.

board<-matrix(c(rep(0,4),3,rep(0,3),1,9,8,rep(0,4),6,rep(0,5),8,0,7,
                rep(0,5),6,2,0,4,0,7,0,0,4,rep(0,4),9,6,0,0,7,0,5,0,3,
                4,8,rep(0,6),1,rep(0,5),7,rep(0,4),5,9,5,rep(0,3),7,rep(0,4)),
              9,9)

plot(c(0,9),c(0,9),type="n",xlab = "",ylab = "",main = "Sudoku puzzle",
     xaxt="n",yaxt="n",bty="n",asp = 1)
for(i in 1:9)
{
  for(j in 1:9)
  {
    rect(i-1,j-1,i,j)
    if(board[10-j,i]!=0)
    {text((i-1)+0.5,(j-1)+0.5,(((board[10-j,i]))))}
  }
}
for(i in 1:3)
{
  for(j in 1:3)
  {
    rect((i-1)*3,(j-1)*3,3*i,3*j,lwd=2)
  }
}

After using the function to solve the puzzle, execute the following lines of code to print the solution. The result object will be created when you solve the puzzle, and will be used by the function below to print the solution.

plot(c(0,9),c(0,9),type="n",xlab = "",ylab = "",main = "Sudoku solved",
     xaxt="n",yaxt="n",bty="n",asp = 1)
for(i in 1:9)
{
  for(j in 1:9)
  {
    rect(i-1,j-1,i,j)
    if(board[10-j,i]!=0)
    {text((i-1)+0.5,(j-1)+0.5,(((board[10-j,i]))))}else{
    text((i-1)+0.5,(j-1)+0.5,(((result[10-j,i]))),col = 2,cex=1.25)}
  }
}
for(i in 1:3)
{
  for(j in 1:3)
  {
    rect((i-1)*3,(j-1)*3,3*i,3*j,lwd=2)
  }
}

(2 points)

F.3.3 Number of calls

How many times does the function solve_sudoku call itself to solve the puzzle?

(4 points)

F.3.4 Number of calls for each cell

Create a 9x9 matrix that contains the number of times the function calls itself for the respective cell in the puzzle.

(6 points)

F.3.5 Reducing recursive calls

Analyze the matrix in the previous question. Edit the function to reduce the number of calls it makes to itself to solve the puzzle. The approach must be general and not specific to this particular puzzle.

Find the number of times the functions calls itself with the improved Sudoku solver to solve the given puzzle.

Also, create a 9x9 matrix that contains the number of times the function calls itself for the respective cell in the puzzle (with the improved Sudoku solver), and print the matrix.

(15 points)